package com.nanbei.dp;

/**
 * @ClassDescription:  两个字符串的删除操作 （先找到最大公共子序列，在用两个数组的长度减去最大公共子序列的长度）
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/10 11:00
 */
public class DeleteOperationForTwoStrings {
    public static void main(String[] args) {
        System.out.println(minDistance("leetcode","etco"));
    }

    public static int minDistance(String word1, String word2){
        char[] aChar = word1.toCharArray();
        char[] bChar = word2.toCharArray();
        int aLength = aChar.length ;
        int bLength = bChar.length ;

        int[][] dp = new int[aLength + 1][bLength + 1];
        for (int i = 1; i <= aLength; i++) {
            char x = aChar[i-1];
            for (int j = 1; j <= bLength; j++) {
                char y = bChar[j-1];
                if (x == y ){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return aLength+bLength-2*dp[aLength][bLength];
    }
}
